1. Field of the Invention
This invention relates generally to forward error correction techniques and computer hardware, and more particularly to a unique forward error correction hardware and method which permits on-line error corrections in the transmission of voice or data and assures virtually error-free transmission.
2. Description of the Prior Art
In the transmission of digitally encoded information of either voice or data, a basic problem is the accuracy of such transmission because of loss of information due to noise or otherwise. Accordingly several techniques have been utilized to identify and correct transmission errors. One such technique is the forward error correction technique which utilizes classic codes, called linear block codes. The linear block codes are chosen so that the elements of the code are the members of a Galois field. The encoding process combines these block codes in a linear way and the decoding process takes them apart in a linear way also. The process of taking them apart is called .-+.syndrome calculation". Since the code was built up linearly, it can be decomposed linearly. Generally a linear feedback shift register is the most cost effective means of doing this. The result of calculating the syndrome is a word having the same length as the word transmitted, which normally contains all 000s in the event that no errors exist. In the event errors exist, the syndrome is non-Zero. Obviously, then the information is in error, but which bits or bits of that information is in error is not yet obvious. In order to recover the error information from a syndrome calculation for a linear code, a Berlekamp algorithm or a Massey algorithm is utilized. The process for doing this is extremely lengthy and cannot be utilized on-line at reasonable data rates, but instead the data is gathered and then batch processed. For example, in a 1200 baud, 600 baud or 300 baud communication line, an extremely high-powered fast computing facility would be necessary. The cost of such a facility would be prohibitive for practical commercial applications. Once the Berlekamp algorithm is complete, however, a relatively simple Chien search is used to establish what the bit pattern actually is, and then the bit patterns are corrected by exclusive-ORing the error positions with the code positions thus inverting the bits that are in error. The Chien search and the actual correction procedure are relatively simple--roughly the same order of magnitude as the syndrome calculation.
What was needed therefore, is to speed up the algorithm calculations so that on-line operation is possible and provide a simple hardware solution which is low in cost and could be utilized in on-line transmission of information.